#include <vector>
#include <queue>
#include <iostream>

using namespace std;

class Solution {
private:
    bool dfs(vector<vector<int>>& grid, vector<vector<bool>>& visited, int i, int j) {
        if (i == grid.size() - 1 && j == grid[0].size() - 1) {
            return true;
        }
        visited[i][j] = true;
        if (i > 0 && !visited[i - 1][j] && (grid[i][j] == 2 || grid[i][j] == 5 || grid[i][j] == 6) && (grid[i - 1][j] == 2 || grid[i - 1][j] == 3 || grid[i - 1][j] == 4)) {
            if (dfs(grid, visited, i - 1, j)) {
                return true;
            }
        }
        if (i < grid.size() - 1 && !visited[i + 1][j] && (grid[i][j] == 2 || grid[i][j] == 3 || grid[i][j] == 4) && (grid[i + 1][j] == 2 || grid[i + 1][j] == 5 || grid[i + 1][j] == 6)) {
            if (dfs(grid, visited, i + 1, j)) {
                return true;
            }
        }
        if (j > 0 && !visited[i][j - 1] && (grid[i][j] == 1 || grid[i][j] == 3 || grid[i][j] == 5) && (grid[i][j - 1] == 1 || grid[i][j - 1] == 4 || grid[i][j - 1] == 6)) {
            if (dfs(grid, visited, i, j - 1)) {
                return true;
            }
        }
        if (j < grid[0].size() - 1 && !visited[i][j + 1] && (grid[i][j] == 1 || grid[i][j] == 4 || grid[i][j] == 6) && (grid[i][j + 1] == 1 || grid[i][j + 1] == 3 || grid[i][j + 1] == 5)) {
            if (dfs(grid, visited, i, j + 1)) {
                return true;
            }
        }
        return false;
    }
public:
    bool hasValidPath(vector<vector<int>>& grid) {
        queue<pair<int, int>> queue;
        queue.push({0, 0});
        vector<vector<bool>> visited(grid.size(), vector<bool>(grid[0].size(), false));
        while (queue.size() > 0) {
            pair<int, int> pt = queue.front();
            queue.pop();
            if (pt.first == grid.size() - 1 && pt.second == grid[0].size() - 1) {
                return true;
            }
            int i = pt.first;
            int j = pt.second;
            visited[i][j] = true;
            if (i > 0 && !visited[i - 1][j] && (grid[i][j] == 2 || grid[i][j] == 5 || grid[i][j] == 6) && (grid[i - 1][j] == 2 || grid[i - 1][j] == 3 || grid[i - 1][j] == 4)) {
                queue.push({i - 1, j});
            }
            if (i < grid.size() - 1 && !visited[i + 1][j] && (grid[i][j] == 2 || grid[i][j] == 3 || grid[i][j] == 4) && (grid[i + 1][j] == 2 || grid[i + 1][j] == 5 || grid[i + 1][j] == 6)) {
                queue.push({i + 1, j});
            }
            if (j > 0 && !visited[i][j - 1] && (grid[i][j] == 1 || grid[i][j] == 3 || grid[i][j] == 5) && (grid[i][j - 1] == 1 || grid[i][j - 1] == 4 || grid[i][j - 1] == 6)) {
                queue.push({i, j - 1});
            }
            if (j < grid[0].size() - 1 && !visited[i][j + 1] && (grid[i][j] == 1 || grid[i][j] == 4 || grid[i][j] == 6) && (grid[i][j + 1] == 1 || grid[i][j + 1] == 3 || grid[i][j + 1] == 5)) {
                queue.push({i, j + 1});
            }
        }
        return false;
    }
};

int main() {
    vector<vector<int>> input = {{2,4,3},{6,5,2}};
    Solution solution;
    solution.hasValidPath(input);
    return 0;
}